這是什麼？

到現在為止，前幾天的內容集中在了解線性數列的資料結構。換個方向想：

• 大區塊的資料結構就是 Array，彼此相連，可以快速取得對應的資料。缺點一次需要的記憶體空間較多，如果空間不足就必須另外請求，直到取得適合的空間才能繼續執行。
• 小區塊的資料空間就是 Linked List，藉由儲存資料與下一個節點的記憶體位置，有效串起成數列。

但要想想，這樣足夠嗎？一次只能找尋一個資料，會不會太慢？假如數列有一萬筆，我們要的資料剛好是第 5566 筆，每次查詢只能從頭開始一個一個找，效率上令人質疑。於是有人想出，同樣的數目下，是否能讓一個資料連結 2 筆、 3 筆以上的資料？

這個想法經過長期的研究後，最終變成資料結構的基礎知識： Tree。

Tree 的基本

是的，真實世界的 組織圖 就是最好的範例。

• 組織圖的最上層 CEO，轉換成 Tree 後稱為 根（root）。
• Tree 擁有組織圖的特徵，具有 階層（level） 概念。
• 每個單位就是 節點（Node）。
• 節點之間的訊息傳遞如同組織圖，要一層一層往上提報。
• 如果沒有下層，稱為 樹葉（Leaf Node）。
• 其他觀念有高度（height）、父節點（parent）、子節點（children）、兄弟節點（siblings）等。

幾個有趣的特性

每個節點的子節點數量是否要統一？

基本上，為了簡化設計上的難度，統一每個節點能夠擁有的最大節點數量，會比較好設計。
換個方向思考：

1. 節點在設計上體現物件導向，每個節點擁有一樣的屬性，在調用相關資料時，會簡單好處理的多。
2. 人性上來說，面對有規律的概念，在了解、操作上，比起無法預測的情境會好上許多。
3. 既然人性對於未知的事物往往會感受到恐懼，那在可預期的程式設計上就不要添加混亂因素。

子節點數量越多是不是越好？

每增加一個節點，表示每個節點要儲存的資訊量會增加：

子節點的數量增加，節點需要的記憶體空間會增加，假設需要的資料是在第三層：

• 二元樹在第二層未使用的節點有一個。
• 四元樹在第二層未使用的節點有三個。
• 八元樹在第二層未使用的節點有七個。

由此可知，除非是需要在一個節點上取得多筆節點資訊，例如地形系統，在繪製時需要取得每一點的多筆資訊才能正確繪製出會面。不然在一般情況上，大多會採用二元樹，避免過多記憶體被浪費掉。

結論

簡單介紹 Tree 的基本概念後，明天要進入 Tree 家族的重頭戲，Binary Tree。
順道一提，LeetCode 的 Tag 為 Tree 的題目，大多以 Binary Tree 為概念在設計題目，藉由此件事可以推論，在程式設計領域中，提起 Tree 要自然而然想到 Binary Tree。